第5章 连通度·匹配·网络流
5.1 连通度(无向图)
5.1.1 割点,割边和块
设 是 中的一个结点, 若 , 则称 是 的一个割点
设 是 中的一条边, 若 , 则称 是 的一条割边
块 : 的极大的没有割点的连通子图称为块
- 若 本身没有割点, 则图 本身就是一个块
- 边集的一个划分
边的剖分运算
- 称边 被剖分, 是指用一条长度为 的道路代替边 , 该道路的内部结点时新增的一个结点
中某边被剖分之后的图记为
-
5.1.2 连通度
点断集,边断集 : 割点和割边的推广
若连通图 删去某些结点之后称为非连通图, 则这些结点组成的集合称为 的一个点断集, 记为 ,
并称 为 的点连通度, 简称 的连通度
若连通图 删去某些边之后称为非连通图, 则这些边组成的集合称为 的一个边断集,简称为断集,
记为 , 并称 为 的边连通度
边连通度, 点连通度反映了连通图的连通程度
是连通图, 是正整数
- 若 , 则称 是 点连通图(简称 连通图)
- 若 , 则称 是 边连通图
非平凡树 是 连通图, 也是 边连通图
回路 是 连通图, 也是 边连通图
至少 阶的块是 连通图, 也是 边连通图
可靠通讯网络的设计
抽象为数学问题
5.2 二部图的匹配
5.2.1 匹配
实际问题
安排工作(二部图的匹配)
安排住宿(每间房能住两个人)
- 结点 : 客人
- 边 : 边关联的两个结点对应的客人可同住
设 是图 的边子集, 若 中任意两边不相邻, 则称 是 的一个匹配
- 与 中的边关联的结点称为 的饱和点, 其余的结点称为 的非饱和点
设 是图 的一个匹配, 如果对 的任意匹配 , 都有 , 则称 是 的一个最大匹配
给定 的一个匹配 , 中属于 与不属于 的边交替出现的道路称为关于 的交错道路
设 是 中关于匹配 的一条交错道路, 如果 的起点和终点都是关于 的非饱和点,
则称 是关于 的可增广道路
5.2.2 二部图的匹配
设 是二部图 的一个匹配, 是 的一个非饱和点
若存在 的一个子集 , 使得 , 中的点都是 的饱和点, 且 ,
则称 是 的不可饱和点
5.3 网络流(netflow)
5.3.1 实际背景
5.3.2 一些定义(网络,可行流,饱和边,最大流,割切)
增流路径
对于 的增流路径 , 令
对 做如下修改,
此时, 仍是容许流, 且流量增加了
5.3.2 Edmonds-Karp Algorithm
5.3.2.1 算法
5.3.2.2 时间复杂度证明
5.3.2.2.1 概念引入
5.3.2.2.2 引理1
5.3.2.2.3 引理2
5.3.2.2.4 引理3
5.3.2.2.5 定理
5.4 作业
5.5 参考答案
-